public class Solution2 {
    //  解法一：递归
    public int uniquePaths1(int m, int n) {
        return dfs1(m, n);
    }

    public int dfs1(int i, int j) {
        if(i == 0 || j == 0) {
            return 0;
        }
        if(i == 1 && j == 1) {
            return 1;
        }
        return dfs1(i - 1, j) + dfs1(i, j - 1);
    }
    //  解法二：记忆化搜索
    public int uniquePaths2(int m, int n) {
        int[][] memo = new int[m + 1][n + 1];
        return dfs2(m, n, memo);
    }

    public int dfs2(int i, int j, int[][] memo) {
        if(memo[i][j] != 0) {
            return memo[i][j];
        }
        if(i == 0 || j == 0) {
            return 0;
        }
        if(i == 1 && j == 1) {
            memo[i][j] = 1;
            return 1;
        }
        memo[i][j] = dfs2(i - 1, j, memo) + dfs2(i, j - 1, memo);
        return memo[i][j];
    }
    //  解法三：动态规划
    public int uniquePaths3(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[1][1] = 1;
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == 1 && j == 1) {
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }
}
